package main.leetcode.clockin.June;

import main.datastruc.ListNode;

import java.util.HashSet;

/**
 * 面试题 02.01.
 *
 * <p>移除重复节点 编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
 *
 * <p>示例1: 输入：[1, 2, 3, 3, 2, 1] 输出：[1, 2, 3]
 *
 * <p>示例2: 输入：[1, 1, 1, 1, 2] 输出：[1, 2]
 *
 * <p>提示：链表长度在[0, 20000]范围内。 链表元素在[0, 20000]范围内。
 *
 * <p>进阶：如果不得使用临时缓冲区，该怎么解决？
 */
public class day26 {
    public static void main(String[] args) {
        System.out.println(
                new day26().removeDuplicateNodes(ListNode.creList(new int[] {1, 2, 3, 3, 2, 1})));
        System.out.println(
                new day26().removeDuplicateNodes(ListNode.creList(new int[] {1, 1, 1, 1, 2})));
    }

    public ListNode removeDuplicateNodes1(ListNode head) {
        if (head == null) {
            return head;
        }
        HashSet<Integer> set = new HashSet<>();
        ListNode pre = head;
        ListNode next = pre.next;
        set.add(head.val);
        while (next != null) {
            if (!set.add(next.val)) {
                pre.next = next.next;
            } else {
                pre = pre.next;
            }
            next = pre.next;
        }
        return head;
    }

    /** 不使用缓冲区，时间换空间 */
    public ListNode removeDuplicateNodes(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode pre = head, next, tmp;
        while (pre != null) {
            tmp = pre;
            next = tmp.next;
            while (next != null) {
                if (next.val == pre.val) {
                    tmp.next = next.next;
                } else {
                    tmp = tmp.next;
                }
                next = tmp.next;
            }
            pre = pre.next;
        }

        return head;
    }
}
